import java.util.HashSet;
import java.util.Set;

public class LongestSubstringWithoutRepeatingCharacters {
    // 滑动窗口 + Set 方法
    public int lengthOfLongestSubstring1(String s) {
        Set<Character> set = new HashSet<>();
        int len = 0;
        // 定义两个指针用于规划窗口大小
        int left = 0, right = 0;
        while (right < s.length()) {
            // 进窗口
            char c = s.charAt(right);
            if (!set.contains(c)) {
                // 如果set集合中没有当前字符, 将当前字符添加进Set中
                set.add(c);
                right++; // right继续扩大窗口
            } else {
                // 如果 set 中含有当前字符, 说明遇到重复的元素了, 需要收缩窗口
                set.remove(s.charAt(left));
                left++;
            }
            // 在本题中, 只要窗口里面有值, 就可以更新结果
            len = Math.max(len, right - left);
        }
        return len;
    }

    // 规则: 窗口内同一个字符不能出现两次
    // 窗口必须合法才能更新结果
    public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        // key-字符 value-字符出现的次数(用int[] 数组模拟)
        int[] hash = new int[128];

        int left = 0, right = 0;
        int len = 0;
        while (right < n) {
            // 1.进窗口
            char in = ch[right];
            hash[in]++;

            // 窗口内同一个字符只能出现一次, 如果当前字符出现两次
            // 则需要不断出窗口, 直到窗口元素合法
            while (hash[in] > 1) {
                char out = ch[left];
                hash[out]--;
                left++;
            }

            // 窗口合法则更新结果
            if (right - left + 1 > len) {
                len = right - left + 1;
            }
            right++;
        }

        return len;
    }
}
